package com.leetcode.根据数据结构分类.图;

import java.util.*;

/**
 * @author: xiaomi
 * @date: 2021/1/21
 * @description: 1489. 找到最小生成树里的关键边和伪关键边
 * https://leetcode-cn.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/
 */
public class C_1489_找到最小生成树里的关键边和伪关键边 {

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0, 1, 1}, {1, 2, 1}, {2, 3, 2}, {0, 3, 2}, {0, 4, 3}, {3, 4, 3}, {1, 4, 6}};
        C_1489_找到最小生成树里的关键边和伪关键边 action = new C_1489_找到最小生成树里的关键边和伪关键边();
        List<List<Integer>> res = action.findCriticalAndPseudoCriticalEdges(n, edges);
        System.out.println("res = " + res);
    }


    /**
     * 如果从 生成MST 来看，只能通过 Prim() 或者 Kruskal() 生成一棵树，
     * 如果通过该课树来判断其中的边是否为关键边 or 伪关键边，就会把问题搞得很复杂：
     * 因为光是遍历完一遍该树是不够的，无法得知还有其他的那些边是需要判断的。
     * --
     * then
     * 我决定通过 Prim() or Kruskal() 生成多个 MST，在通过 MST 集合判断最后的答案。
     * --
     * 这种通过 生成所有的 MST 的方法，太暴力解法了。但是感觉用 kruskal 和 Prim 都很难实现。
     * 看来这就是为何科学家的算法只求出来一种解法，而没有深入到所有的解法！
     * --
     * 那么我看完题解以后再来尝试一下吧。
     *
     * @param n     顶点个数
     * @param edges 边的信息
     * @return
     */
    public List<List<Integer>> findCriticalAndPseudoCriticalEdgesTry(int n, int[][] edges) {
        //记录 index - edge info
        HashMap<Integer, int[]> map = new HashMap<>();
        //提供的边的长度
        int edgeSize = edges.length;
        for (int i = 0; i < edgeSize; i++) {
            map.put(i, edges[i]);
        }
        PriorityQueue<Map.Entry<Integer, int[]>> heap = new PriorityQueue<>(new Comparator<Map.Entry<Integer, int[]>>() {
            @Override
            public int compare(Map.Entry<Integer, int[]> o1, Map.Entry<Integer, int[]> o2) {
                return o1.getValue()[2] - o2.getValue()[2];
            }
        });
        for (Map.Entry<Integer, int[]> item :
                map.entrySet()) {
            heap.offer(item);
        }

        InnerUnionFind unionFind = new InnerUnionFind(n);
        //MST 所需要的 最小边的数量
        int edgeSize4MST = n - 1;
        //当前边的数量
        int count = 1;
        Map.Entry<Integer, int[]> curEntry = heap.poll();
        int[] curEdge = curEntry.getValue();
        //MST 的权重和
        int weightSum = curEdge[2];
        unionFind.union(curEdge[0], curEdge[1]);
        //第一个最小生成树的 边在 edges 中的索引
        List<Integer> firstMST = new ArrayList<>();
        firstMST.add(curEntry.getKey());
        while (count < edgeSize4MST) {
            curEntry = heap.poll();
            curEdge = curEntry.getValue();
            if (unionFind.isSame(curEdge[0], curEdge[1])) {
                curEntry = heap.poll();
                curEdge = curEntry.getValue();
            }
            //直到找到非环的 min edge
            unionFind.union(curEdge[0], curEdge[1]);
            count++;
            weightSum += curEdge[2];
            firstMST.add(curEntry.getKey());
        }
        //此时找到了 MST 的 weight + firstMST

        return null;
    }

    /**
     * 既然从起点考虑无解，那么从结果分析：
     * 关键边：如果少了该边，要么无法生成 MST，要么 weighSum 增大；
     * 伪关键边：如果少了该边，依然连通 + weighSum 不变；
     * 还有一个关键的隐含性质：如果先连通伪关键边，weighSum 不变！
     * --
     * 思路是清晰的，但是转换比较复杂，需要记笔记。
     * @param n     顶点的个数
     * @param edges 图中所有的边
     * @return
     */
    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        //由于结果需要 edges 中的结果个数，所以又想节省空间，就利用了一个 列长度为 4的数组
        int m = edges.length;
        // 初始化答案列表
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        res.add(new ArrayList<>());
        if (n==2){
            //如果只有两个点
            res.get(0).add(0);
            return res;
        }

        //m 行 4 列的二维数组
        int[][] newEdges = new int[m][4];
        for (int i = 0; i < m; i++) {
            newEdges[i] = new int[]{i, edges[i][0], edges[i][1], edges[i][2]};
        }
        //将 newEdges 按照权重进行排序，以便复用
        Arrays.sort(newEdges, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[3] - o2[3];
            }
        });
        //生成 MST 的边的大小
        int edgeSize = n - 1;
        InnerUnionFind unionFind = new InnerUnionFind(n);
        int weightSum = 0, count = 0;
        //1.得到 MST 的 weight sum
        int minWeightSum = getMST(newEdges, edgeSize, unionFind, count, weightSum);




        //2.判断关键边
        int len = edges.length;
        //减少后的边
        int tempSize = len - 1;
        for (int i = 0; i < len; i++) {
            //2.1 删除 edges[i] 的边
            //2.1.1 构建一个临时边的数组作为被删除的边
            int[][] tempNewEdges = getDeletedEdges(i, tempSize, newEdges);

            InnerUnionFind tempUnionFind = new InnerUnionFind(n);
            int ws = getMST(tempNewEdges, edgeSize, tempUnionFind, 0, 0);
            if (ws > minWeightSum) {
                //如果删除之后变大，说明是 关键边
                res.get(0).add(newEdges[i][0]);
            }
        }
        //3.判断伪关键边
        for (int i = 0; i < len; i++) {
            if (res.get(0).contains(newEdges[i][0])) {
                //如果已经是关键边，那就跳过判断
                continue;
            }

            InnerUnionFind tempUnionFind = new InnerUnionFind(n);
            tempUnionFind.union(newEdges[i][1], newEdges[i][2]);
            int ws = getMST(newEdges, edgeSize, tempUnionFind, 1, newEdges[i][3]);
            if (ws == minWeightSum){
                res.get(1).add(newEdges[i][0]);
            }
        }

        return res;
    }

    private int[][] getDeletedEdges(int i, int tempSize, int[][] newEdges) {
        int[][] tempNewEdges = new int[tempSize][4];
        //一个标志位，用来标志是否已经遇到删除的边
        boolean flag = false;
        for (int j = 0; j < tempSize; j++) {
            if (!flag && j == i) {
                flag = true;
            }
            if (flag) {
                tempNewEdges[j] = newEdges[j + 1];
            } else {
                tempNewEdges[j] = newEdges[j];
            }
        }
        return tempNewEdges;
    }

    /**
     * 根据 顺序排序的边信息 和 顶点个数 获取一棵 MST
     * --
     * 1.生成一棵 MST，算出 权重和 W。
     * --
     *
     * @param array     数组
     * @param edgeSize  边的大小
     * @param unionFind 并查集
     * @param count     边的计数
     * @param weight    权重和
     * @return
     */
    private int getMST(int[][] array, int edgeSize, InnerUnionFind unionFind, int count, int weight) {
        //array 中的边的索引
        int index = 0;
        int len = array.length;
        while (count < edgeSize && index < len) {
            while (index < len && unionFind.isSame(array[index][1], array[index][2])) {
                index++;
            }
            if (index == len) {
                return Integer.MAX_VALUE;
            }
            unionFind.union(array[index][1], array[index][2]);
            count++;
            weight += array[index][3];
        }
        return weight;
    }


    /**
     * 并查集
     */
    class InnerUnionFind {
        int[] parents;
        int[] ranks;

        public InnerUnionFind(int capacity) {
            this.parents = new int[capacity];
            this.ranks = new int[capacity];
            for (int i = 0; i < capacity; i++) {
                this.parents[i] = i;
                this.ranks[i] = 1;
            }
        }

        boolean isSame(int index1, int index2) {
            return find(index1) == find(index2);
        }

        int find(int index) {
            if (index != parents[index]) {
                parents[index] = find(parents[index]);
            }
            return parents[index];
        }

        void union(int index1, int index2) {
            int p1 = find(index1);
            int p2 = find(index2);
            if (p1 == p2) {
                return;
            }
            //需要合并
            if (ranks[p1] == ranks[p2]) {
                parents[p1] = p2;
                ranks[p2]++;
            } else if (ranks[p1] < ranks[p2]) {
                parents[p1] = p2;
            } else {
                parents[p2] = p1;
            }
        }

    }
}
